#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;

namespace chaos
{
	/* 定义结点 */
	template<class T>
	struct ListNode {
		T _data;				  // 用来存放结点的数据
		ListNode<T>* _next;       // 指向后继结点的指针
		ListNode<T>* _prev;	      // 指向前驱结点的指针

		ListNode(const T& data = T())   // 全缺省构造（初始化）
			: _data(data)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	/* 定义迭代器 */
	template<class T, class Ref, class Ptr>
	struct __list_iterator {
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;    // 为了方便我们重命名为self

		typedef Ref reference;
		typedef Ptr pointer;

		Node* _node;

		__list_iterator(Node* x)
			: _node(x)
		{}

		/* 解引用 */
		Ref operator*() {
			return _node->_data;       // 返回结点的数据
		}
		Ptr operator->() {
			return &_node->_data;
		}

		/* ++it */
		self& operator++() {
			_node = _node->_next;  // 让 _node 指向下一个结点
			return *this;  // 返回加加后的值
		}
		/* it++ */
		self operator++(int) {
			self tmp(*this);   // 拷贝构造一个tmp存储原来的值
			_node = _node->_next;
			return tmp;
		}
		/* != */
		bool operator!=(const self& it) {
			return _node != it._node;  // 它们结点的指针不一样吗？T or F
		}

		/* --it */
		self& operator--() {
			_node = _node->_prev;
			return *this;
		}
		/* it-- */
		self operator--(int) {
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
	};

	///* 定义const迭代器 */
	//template<class T>
	//struct __const_list_iterator {
	//	typedef ListNode<T> Node;
	//	Node* _node;

	//	__const_list_iterator(Node* x)
	//		: _node(x)
	//	{}
	//	/* 解引用 */
	//	const T& operator*() {
	//		return _node->_data;       // 返回结点的数据
	//	}
	//	/* ++it */
	//	__const_list_iterator<T>& operator++() {
	//		_node = _node->_next;  // 让 _node 指向下一个结点
	//		return *this;  // 返回加加后的值
	//	}
	//	/* it++ */
	//	__const_list_iterator<T> operator++(int) {
	//		__const_list_iterator<T> tmp(*this);   // 拷贝构造一个tmp存储原来的值
	//		_node = _node->_next;
	//		return tmp;
	//	}
	//	/* != */
	//	bool operator!=(const __const_list_iterator<T>& it) {
	//		return _node != it._node;  // 它们结点的指针不一样吗？T or F
	//	}
	//	/* --it */
	//	__const_list_iterator<T>& operator--() {
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	/* it-- */
	//	__const_list_iterator<T> operator--(int) {
	//		__list_iterator<T> tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//};

	/* 定义链表 */
	template<class T>
	class list {
		typedef ListNode<T> Node;      // 重命名为Node
	public:
		/* 迭代器 */
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		iterator begin() {
			return iterator(_pHead->_next);
		}
		iterator end() {
			return iterator(_pHead);
		}
		const_iterator begin() const {
			return const_iterator(_pHead->_next);
		}
		const_iterator end() const {
			return const_iterator(_pHead);
		}

		/* 构造函数：初始化头结点 */
		list() {
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
		}
		list(size_t n, const T& val = T()) {   // 初始化n个结点
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
			for (size_t i = 0; i < n; i++) {
				push_back(val);
			}
		}
		list(int n, const T& val = T()) {   // 初始化n个结点
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
			for (int i = 0; i < n; i++) {
				push_back(val);
			}
		}

		template<class InputIterator>
		list(InputIterator first, InputIterator last) {
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;

			while (first != last) {
				push_back(*first);
				first++;
			}
		}
		/* 拷贝构造（现代写法）：L2(L1) */
		list(const list<T>& L) {
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;

			list<T> tmp(L.begin(), L.end());
			swap(_pHead, tmp._pHead);
		}

		/* 拷贝构造：L2(L1) */
		/*list(const list<T>& L) {
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
			for (auto e : L) {
				push_back(e);
			}
		}*/

		///* 赋值：L2 = L1 */
		//list<T>& operator=(list<T> L) {
		//	if (this != &L) {
		//		clear();
		//		for (auto e : L) {
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}


		/* 赋值（现代写法）：L2 = L1 */
		list<T>& operator=(list<T> L) {
			swap(_pHead, L._pHead);
			return *this;
		}


		/* 在pos位置前插入 */
		void insert(iterator pos, const T& x) {
			Node* cur = pos._node;     // 找到pos位置的结点
			Node* cur_prev = cur->_prev;     // 因为要在pos位置前插入，所以要找到当前pos位置的前一个结点
			Node* new_node = new Node(x);  // 创建新节点

			// 缝合： cur_prev <-> new_node <-> cur
			cur_prev->_next = new_node;
			new_node->_prev = cur_prev;
			new_node->_next = cur;
			cur->_prev = new_node;
		}

		/* 尾插：push_back */
		void push_back(const T& x) {
			//Node* pTail = _pHead->_prev;     // pHead的前驱就是pTail
			//Node* new_node = new Node(x);    // 创建新结点（会调用构造，自动创建）
			//
			//pTail->_next = new_node;
			//new_node->_prev = pTail;
			//new_node->_next = _pHead;
			//_pHead->_prev = new_node;

			insert(end(), x);   // 在end(头结点)前插入，即尾插
		}

		/* 头插：push_front */
		void push_front(const T& x) {
			insert(begin(), x);  // 在begin（头结点的下一个结点）前插入，即头插
		}


		/* 任意位置删除 */
		iterator erase(iterator pos) {
			assert(pos != end());   // 防止头结点被删除

			Node* cur = pos._node;   // 找到pos位置的结点
			Node* cur_prev = cur->_prev;   // 找到pos的前驱
			Node* cur_next = cur->_next;   // 找到pos的后继

			// 删除cur
			delete cur;

			// 缝合：  cur_prev <-> cur(删) <-> cur_next
			cur_prev->_next = cur_next;
			cur_next->_prev = cur_prev;

			return iterator(cur_next);
		}

		/* 尾删 */
		void pop_back() {
			erase(--end());  // 删除最后一个元素，即尾结点
		}

		/* 头删 */
		void pop_front() {
			erase(begin());  // 删除头结点的下一个结点（即begin位置的结点）
		}

		/* 清空链表所有数据 */
		void clear() {
			利用迭代器去遍历整个链表
				//iterator it = begin();
				//while (it != end()) {
				//	iterator del = it++;  // 巧妙利用后置++的特性
				//	delete del._node;  // 删除当前结点，后置++生效
				//}

				删完之后我们还需要将其恢复到初始状态
				//_pHead->_next = _pHead;
				//_pHead->_prev = _pHead;

				iterator it = begin();
			while (it != end()) {
				// iterator del = it++;
				erase(it++);   // 直接反复调用erase删除结点
			}
		}

		~list() {
			// 清空链表有效数据
			clear();
			// 干掉头结点
			delete _pHead;
			_pHead = nullptr;
		}

	private:
		Node* _pHead;
	};

	void print_list(const list<int>& L) {
		list<int>::const_iterator it = L.begin();
		while (it != L.end()) {
			// *it = 100;
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}


	void test_list1() {
		list<int> L;
		L.push_back(1);
		L.push_back(2);
		L.push_back(3);
		L.push_back(4);

		list<int>::iterator it = L.begin();
		while (it != L.end()) {
			*it *= 2;
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

	void test_list2() {
		list<int> L;
		L.push_back(2);
		L.push_back(4);
		L.push_back(6);
		L.push_back(8);

		print_list(L);
	}


	struct Date {
		int _year;
		int _month;
		int _day;

		Date(int year = 1, int month = 1, int day = 1)
			: _year(year)
			, _month(month)
			, _day(day)
		{}
	};

	void test_list3() {
		list<Date> L;
		L.push_back(Date(2022, 5, 1));
		L.push_back(Date(2022, 5, 2));
		L.push_back(Date(2022, 5, 3));

		list<Date>::iterator it = L.begin();
		while (it != L.end()) {
			cout << it->_year << "/" << it->_month << "/" << it->_day << endl;
			it++;
		}
		cout << endl;
	}

	void test_list4() {
		list<int> L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);

		list<int> L2(L1);
		for (auto e : L2) cout << e << " ";
	}

	void test_list5() {
		list<int> L;
		L.push_back(1);
		L.push_back(2);
		L.push_back(3);
		cout << "删除前：";
		print_list(L);

		cout << "删除后：";
		L.clear();
		print_list(L);
	}
}
